Longest increasing subsequenc [Binary Search, DP]

Time: O(NLogN); Space: O(N); medium

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation:

  • The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [5,4,1,2,3]

Output: 3

Explanation:

  • LIS is [1,2,3]

Example 3:

Input: nums = [4,2,4,5,3,7]

Output: 4

Explanation:

  • LIS is [2,4,5,7]

Notes:

  • There may be more than one LIS combination, it is only necessary for you to return the length.

  • Your algorithm should run in O(n2) complexity.

Follow up:

  • Could you improve it to O(n log n) time complexity?

1. Binary Search [O(NLogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        LIS = []

        def insert(target):
            left, right = 0, len(LIS) - 1

            # Find the first index "left" which satisfies LIS[left] >= target
            while left <= right:
                mid = left + (right - left) // 2
                if LIS[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1

            # If not found, append the target.
            if left == len(LIS):
                LIS.append(target)
            else:
                LIS[left] = target

        for num in nums:
            insert(num)

        return len(LIS)

[2]:

s = Solution1()

nums =  [10,9,2,5,3,7,101,18]
assert s.lengthOfLIS(nums) == 4

nums = [5,4,1,2,3]
assert s.lengthOfLIS(nums) == 3

nums = [4,2,4,5,3,7]
assert s.lengthOfLIS(nums) == 4

2. Traditional DP solution [O(N^2), O(N)]

[3]:

class Solution2(object):
    """
    Time:  O(N^2)
    Space: O(N)
    """
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []  # dp[i]: the length of LIS ends with nums[i]

        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp) if dp else 0

[4]:

s = Solution2()

nums =  [10,9,2,5,3,7,101,18]
assert s.lengthOfLIS(nums) == 4

nums = [5,4,1,2,3]
assert s.lengthOfLIS(nums) == 3

nums = [4,2,4,5,3,7]
assert s.lengthOfLIS(nums) == 4